package top.fengleifeng.question;

import top.fengleifeng.util.Constants;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: leetcode-test
 * @description: 在一棵无限的二叉树上，每个节点都有两个子节点，树中的节点 逐行 依次按 “之” 字形进行标记。
 * <p>
 * 如下图所示，在奇数行（即，第一行、第三行、第五行……）中，按从左到右的顺序进行标记；
 * <p>
 * 而偶数行（即，第二行、第四行、第六行……）中，按从右到左的顺序进行标记。
 * <p>
 * <p>
 * <p>
 * 给你树上某一个节点的标号 label，请你返回从根节点到该标号为 label 节点的路径，该路径是由途经的节点标号所组成的。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：label = 14
 * 输出：[1,3,4,14]
 * 示例 2：
 * <p>
 * 输入：label = 26
 * 输出：[1,2,6,10,26]
 *  
 * <p>
 * 提示：
 * <p>
 * 1 <= label <= 10^6
 * 通过次数5,461提交次数7,840
 * 在真实的面试中遇到过这道题？
 * <p>
 * <p>
 * 1
 * 2                    3
 * 4         5          6          7
 * 8     9   10    11   12    13   14    15
 * ....
 * <p>
 * 作者：gre-z
 * 链接：https://leetcode-cn.com/problems/path-in-zigzag-labelled-binary-tree/solution/jian-dan-yi-dong-de-gong-shi-shi-jian-guo-100-by-a/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 * <p>
 * 作者：gre-z
 * 链接：https://leetcode-cn.com/problems/path-in-zigzag-labelled-binary-tree/solution/jian-dan-yi-dong-de-gong-shi-shi-jian-guo-100-by-a/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/path-in-zigzag-labelled-binary-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author: fengleifeng
 * @create: 2020-09-07 17:54
 **/
public class Num1104二叉树寻路TODO {
    /**
     * 每一行的数量是固定的 2的n次方
     * 所以每一行的排序顺序是可以确定的   奇数正序，偶数逆序
     */
    class Solution {
        /**
         * 主要分成5大部分：
         * 1.把头结点1放入list，因为不管哪个点最终都需要1这个节点，如果label是1，直接返回
         * 2.求出来label是在哪一行，用的log2求的
         * 3.把label的序号转化为没有任何翻转的情况下的值
         * 4.求出来所有的没有任何翻转的节点位置
         * 5.把奇数行的节点翻转过来，最后返回
         *
         * @param label
         * @return
         */
        public List<Integer> pathInZigZagTree(int label) {
            List<Integer> res = new ArrayList<>();
            res.add(1);
            if (label == 1) {
                return res;
            }
            int last = (int) Math.floor(Math.log(label) / Math.log(2));
            if ((last&1)==1) {
                int rightLen=(1<<last+1)-label-1;
                label =(1<<last)+rightLen;
            }

            while (label!=1){
                res.add(1,label);
                label=label>>1;
            }

            for (int i=0;i<res.size();i++){
                if ((i&1)==1){
                    int rightLen=(1<<i+1)-res.get(i)-1;
                    res.set(i,(1<<i)+rightLen);
                }
            }
            return res;
        }
/*        public List<Integer> pathInZigZagTree(int label) {
            List<Integer> result = new LinkedList<>();
            int temp = label;
            int level = getLevel(label);//第n行
            int count = getCount(level, label);//第几行的第几个
            System.out.println(level + ":" + count);
            result.add(label);
            for (int i = level - 1; i > 0; i--) {
                //第i行第几个
                count = (count + 1) / 2;//第几个
                int num = getInt(i, count);
                System.out.println(i + ":" + count + ":" + num);
//                int nowNum = (int) Math.pow(2, nowLine - 1) + count;
//                if (nowLine % 2 == 0) {
//                    nowNum = (int) Math.pow(2, nowLine) - count + 1;
//                }
//                result.add(nowNum);
            }
            return result;
        }

        public int getInt(int level, int count) {
            if (level % 2 == 0) {
                count = (int) Math.pow(2, level ) - count;
            } else {
                count = (int) Math.pow(2, level - 2) + count;
            }
            return count;
        }
        //第几个
        public int getCount(int level, int label) {
            if (level % 2 == 0) {
                label = (int) Math.pow(2, level) - label;
            } else {
                label = label - (int) Math.pow(2, level - 1) + 1;
            }
            return label;
        }
        *//**
         * 第n行
         *
         * @return
         *//*
        public int getLevel(int label) {
            int level = 1;
            int num = 1;
            while (label - num > 0) {
                label = label - num;
                num = num * 2;
                level++;
            }
            return level;
        }*/

    }

    public static void main(String[] args) {
        int label = 14;
        List<Integer> list = new Num1104二叉树寻路TODO().new Solution().pathInZigZagTree(label);
        Constants.pringLinkedList(list);
    }
}
